package leetcode.sort;

import leetcode.每日一题.八皇后;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2022/9/23 5:50 PM
 * @description：
 */
public class TestSort {

    @Test
    public void test() {
        int[] arr = {-9, 23, 0, 10, -567, 70, 70, 70};

        // quickSort(arr, 0, arr.length - 1);
        // bubbleSort(arr);
        // selectSort(arr);
        // insertSort(arr);
        // shellSort(arr);
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
        System.out.println(Arrays.toString(arr));
    }

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int l = left;
        int r = right;
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) l++;
            nums[r] = nums[l];
            nums[l] = pivot;
        }
        quickSort(nums, left, l - 1);
        quickSort(nums, l + 1, right);
    }

    public void bubbleSort(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            boolean isCharge = false;
            for (int j = 0; j < len - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    isCharge = true;
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
            if (!isCharge) return;
        }
    }

    public void selectSort(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < len; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            int tmp = nums[minIdx];
            nums[minIdx] = nums[i];
            nums[i] = tmp;
        }
    }

    /**
     * 原始数组： 101 34 119 1
     * 第一次插入： 34 101 119 1
     * 第二次插入： 34 101 119 1
     * 第三次插入： 1 34 101 119
     */
    public void insertSort(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            int insertIdx = i - 1;
            int insertVal = nums[i];
            while (insertIdx >= 0 && insertVal < nums[insertIdx]) {
                nums[insertIdx + 1] = nums[insertIdx];
                insertIdx--;
            }
            if (insertIdx + 1 != i) {
                nums[insertIdx + 1] = insertVal;
            }
        }
    }

    public void shellSort(int[] nums) {
        int len = nums.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < len; i++) {
                int insertIdx = i - gap;
                int insertVal = nums[i];
                while (insertIdx >= 0 && insertVal < nums[insertIdx]) {
                    nums[insertIdx + gap] = nums[insertIdx];
                    insertIdx -= gap;
                }
                if (insertIdx + gap != i) {
                    nums[insertIdx + gap] = insertVal;
                }
            }
        }
    }

    public void mergeSort(int[] nums, int left, int right, int[] tmp) {
        if (left < right) {
            int mid = left + right >> 1;
            mergeSort(nums, left, mid, tmp);
            mergeSort(nums, mid + 1, right, tmp);
            merge(nums, left, mid, right, tmp);
        }
    }

    private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid || j <= right) {
            tmp[t++] = (i <= mid ? nums[i] : Integer.MAX_VALUE) < (j <= right ? nums[j] : Integer.MAX_VALUE) ? nums[i++] : nums[j++];
        }
        t = 0;
        int tmpLeft = left;
        while (tmpLeft <= right) {
            nums[tmpLeft++] = tmp[t++];
        }
    }

    public void heapSort(int[] nums) {

    }
}
